package com.banmao.algorithm.No1To100.No86;

import lombok.Data;

public class Solution {

    public ListNode partition(ListNode head, int x) {

        if(head == null || head.next == null) {
            return head;
        }
        // 用两个虚拟头节点
        // 一个用于生成值小于x的链表，另一个用于生成值大于x的链表
        ListNode dummy = new ListNode();
        ListNode dummy2 = new ListNode();

        ListNode p1 = dummy, p2 = dummy2;
        ListNode p = head;

        while (p != null) {
            if(p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            }
            if(p.val < x) {
                p1.next = p;
                p1 = p1.next;
            }
            // 断开原链表的next
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }

        // 连接两个链表
        p1.next = dummy2.next;
        return dummy.next;

    }

}

@Data
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
